The present application relates to an encoding method, an encoding apparatus, a decoding method, and a decoding apparatus. More particularly, the invention relates to an encoding method, in encoding apparatus, a decoding method, and a decoding apparatus for reducing the bit error rate (BER) of transmitted information and the probability of undetected errors in the information.
Many recording and reproducing apparatuses and communication apparatuses have been designed to reduce the bit error rate of digitally transmitted information typically by encoding input information sequences before they are transmitted. FIG. 1 is a block diagram showing a configuration of a typical recording and reproduction system 1 made up of a recording apparatus 11 and a reproducing apparatus 12.
In FIG. 1, an information sequence from the user side (i.e., input information sequence) is input to an encoding section 21 and encoded at a k/n ratio into all encoded sequence (where, “k” stands for an information word length and “n” for a code word length, and k/n is called a code rate). For encoding purposes, a plurality of encoding methods are often used in combination including an encryption code, an error-correcting code, and an RLL (run-length limited) code.
The encoded sequence is input to a recording section 22. In turn, the recording section 22 records the sequence to a recording medium, not shown, using an optical pickup, a magnetic head or other suitable means. Recording signals from the recording section 22 are input to the reproducing apparatus 12.
More specifically, the recording signals from the recording section 22 are input to a reproducing section 31 of the reproducing apparatus 12. In turn, the reproducing section 31 converts the signals from the recording medium, not shown, to analog reproduction signals using an analog optical pickup, a magnetic head or other suitable means. The analog reproduction signals are equalized by an analog equalizer, not shown, into a predetermined target equalization characteristic before being converted periodically into digital reproduction signals by an A/D (analog/digital) converting section 32. The A/D converting section 32 includes a phase locked-loop circuit, not shown.
The digital reproduction signals are converted by a code detecting section 33 into a detected code sequence or a posterior probability information sequence that is input to a decoding section 34. The decoding section 34 decodes the input sequence at an n/k ratio into a detected information sequence.
If the equalization by the analog equalizer or the like is not sufficient, there may be disposed a digital equalizer between the A/D converting section 32 and the code detecting section 33. In recent years, it has become customary to use a soft-decision detector such as a Viterbi detector in the code detecting section 33. If the decoding section 34 adopts iterative decoding, then a posterior probability detector may be used in the code detecting section 33 in some cases.
Apart from the typical recording and reproduction system 1 composed of the recording apparatus 11 and reproducing apparatus 12 as shown in FIG. 1, there may be provided a transmitting and receiving system made up of a transmitting apparatus and a receiving apparatus. The transmitting apparatus may include a transmitting section replacing the recording section 22 and the receiving apparatus may have a receiving section replacing the reproducing section 31. In this transmitting and receiving system, the encoding section 21, A/D converting section 32, code detecting section 33, and decoding section 34 still carry out the same processes as in the recording and reproduction system 1.
Various encoding methods are considered for use by the encoding section 21 of the recording apparatus 11 in FIG. 1. For storage system purposes, an RLL code and an error-correcting code are generally used in combination.
The Reed-Solomon code has long been utilized as an error-correcting code. In recent years, the so-called low-density parity-check code has come into general use as a highly effective error-correcting code.
As a variation of the RLL code, there is a so-called (d, k) RLL code whereby the maximum run length of 0's between 1's is limited to “k” and the minimum run length of 0's between 1's is limited to “d” in an encoded sequence before NRZI (non-return to zero invert) modulation. In NRZI modulation, the polarity of recording or transmission signals is inverted on 1's and not inverted on 0's.
What is known as an MTR (maximum transition run) code is a code whereby the maximum run length of 1's is set at least to two and is finite in an encoded sequence before NRZI modulation. Any code whereby the maximum run length of 1's is set to one is the same as minimum run-length limited codes that have long been known, so that that code generally is not called an MTR code.
Techniques related to the MTR code are disclosed illustratively by a non-patent document “IEEE Trans. Magn. 32, p. 3992, 1996” by J. Moon and B. Bricker (called the Non-Patent Document 1 hereunder), and U.S. Pat. No. 5,859,601, January 1999, by J. Moon and B. Bricker (called the Patent Document 1 hereunder). According to these documents, it is possible to constitute a code with a code rate of 7/8 if the maximum run length of the code (MTR=2) code is at least eight.
The expression “maximum transition run (MTR)” indicating the maximum number of continuous 1's in an encoded sequence was first used in the above-cited Non-Patent Document 1. However, codes whereby the maximum number of continuous 1's is set to a finite number had been known before publication of that document. A major feature of the MTR code is that by limiting the maximum transition run of 1's to a small number, the code allows a trellis of received signal detectors with their partial responses equalized to remove or reduce encoded sequences of small square Euclidean distances, thereby affording a coding gain to the system in use. In the case of codes whereby the maximum transition run of 1's is limited but is set to a large number, the coding gain tends to be very small. For this reason, any code whereby the maximum transition run of 1's is limited approximately to between two and four for coding gain enhancement is often called an MTR code.
The performance of MTR codes whereby the maximum transition run of 1's is limited to between two and four is illustratively discussed in detail in a non-patent document “Application of Distance Enhancing Codes,” IEEE Trans. Magn., Vo. 37, No. 2, pp. 762-767, March 2001 (called the Non-Patent Document 2 hereunder).
If the signal-to-noise ratio (SNR) of received signals is assumed to be constant, then the gain for the code detector in use is greater the larger the maximum transition run of 1's. Generally, stricter MTR constraints entail lower code rates that can be attained as well as deteriorated SNR's. Thus optimal MTR constraints for the code of interest are correlated with the signal transmission characteristic of the system in use.
FIG. 2 is a tabular view showing how the Shannon capacity of a given code is dependent on MTR constraints where encoded sequences are not limited by maximum run lengths. A Shannon capacity signifies a theoretical maximum code rate that may be attained by a code subject to constraints. That is, it is theoretically possible to design a code with its code rate lower than the applicable Shannon capacity. It should be noted that the example in FIG. 2 has no consideration for known methods whereby the MTR constraints are set in a time-varying structure in which even-numbered and odd-numbered bits occur, say, every two bits and every three bits respectively.
Where the Shannon capacities of codes are dependent on MTR constraints as shown in FIG. 2 and where encoded sequences are not subject to maximum run length limits, the Shannon capacity is illustratively 0.6942 for MTR=1, 0.8791 for MTR=2, 0.9468 for MTR=3, 0.9752 for MTR=4, and 0.9881 for MTR=5.
Most storage systems and communication systems perform their internal processes in units of bytes (i.e., 8 bits). It follows that these systems find it convenient if the information word length of the RLL code is a multiple of eight. If codes of which the information word length is a multiple of one byte are assumed, then it is possible to design a code of 8/10 conversion for MTR=2 (code rate: 0.8), a code of 16/17 conversion for MTR=3 (code rate: 0.9411 . . . ), and a code of 32/33 conversion for MTR=4 (code rate: (0.9696 . . . ). The code for actual use by a system, however, demands limiting the maximum run length of encoded sequences at the same time. Thus depending on the maximum run length limit applicable to the code in use, that code may or may not be designed for a high code rate under the same MTR constraints.
A (0, 11)16/17 RLL code is a code (MTR=3), whereby the maximum run length of encoded sequences is limited to 11, as disclosed illustratively by T. Nishiya, K. Tsukano, T. Hirai. S. Mita and T. Nara in a non-patent document “Rate 16/17 Maximum Transition Run (3; 11) Code on an EEPRML Channel with an Error-Correcting Postprocessor,” IEEE Trans. Magn. Vol. 35, No. 5, pp. 4378-4386, September 1999 (called the Non-Patent Document 3 hereunder).
The 16/17 code disclosed in the Non-Patent Document 3 above is a variable-length code whereby information words are converted to temporary words in accordance With a basic code conversion table before the temporary code words are converted to code words according to a violation code conversion table involving code word look-ahead operations.
Variable-length codes generally offer higher code rates and, given the same code rate, work as an efficient code scheme with shorter-code lengths than fixed-length codes that do not demand code word look-ahead operations.
What follows is a description of how the 16/17 code disclosed in the Non-Patent Document 3 above works as an encoding method. Sixteen-bit information words are converted to 17-bit temporary code words in accordance with a basic code conversion table so that the maximum run length of 0's is 10 and the maximum run length of 1's is 3 per temporary code word and that the maximum run length of 1's at the beginning and at the end of each temporary code word is 2. There exist 65,546 17-bit sequences that meet these constraints. As many as 216 (=65,546) 17-bit sequences are selected as the temporary code words and included in the basic code conversion table. Some of these temporary code words can violate the constraints of MTR=3 and k=11 at a connection between two code words. In such cases, the words are encoded according to a violation code conversion table.
FIG. 3 is a tabular view showing an eight-bit violation code conversion table disclosed by the Non-Patent Document 3 above for use at connections between codes. In FIG. 3, each comma (,) indicates the boundary between two consecutive code words.
In the violation code conversion table of FIG. 3, rule number 1 indicates that if the last 4 bits of a temporary code word 1 are “0011” and the first 4 bits of a temporary code word 2 immediately following the temporary code word 1 are “1100,” then the last 4 bits of the temporary code word 1 are converted to “0111” and the first 4 bits of the temporary code word 2 are converted to “0100” as a definitive code word each.
Likewise, rule number 2 indicates that if the last 4 bits of the temporary code word 1 are “0011” and the first 4 bits of the temporary code 2 are “1101” these bits are converted to “0111” and “0101” respectively; rule number 3 indicates that if the last 4 bits of the temporary code word 1 are “1011” and the first 4 bits of the temporary code 2 are “1100,” these bits are converted to “1010” and “1110” respectively; rule number 4 indicates that if the last 4 bits of the temporary code word 1 are “0111” and the first 4 bits of the temporary code 2 are “1101” these bits are converted to “1000” and “1110” respectively; and rule number 5 indicates that if the last 4 bits of the temporary code word 1 are “0000” and the first 4 bits of the temporary code 2 are “0000,” these bits are converted to “0010” and “1100” respectively.
Similarly, rule number 6 indicates that if the last 4 bits of the temporary code word 1 are “0000” and the first 4 bits of the temporary code 2 are “0001,” these bits are converted to “0000” and “1110” respectively; rule number 7 indicates that if the last 4 bits of the temporary code word 1 are “0000” and the first 4 bits of the temporary code 2 are “0010,” these bits are converted to “0111” and “0010” respectively; rule number 8 indicates that if the last 4 bits of the temporary code word 1 are “0000” and the first 4 bits of the temporary code 2 are “0011,” these bits are converted to “0111” and “0110” respectively; rule number 9 indicates that if the last 4 bits of the temporary code word 1 are “1000” and the first 4 bits of the temporary code 2 are “0000,” these bits are converted to “0111,” and “0000” respectively; rule number 10 indicates that if the last 4 bits of the temporary code word 1 are “0100” and the first 4 bits of the temporary code 2 are “0000,” these bits are convened to “0100” and “1110” respectively; and rule number 11 indicates that if the last 4 bits of the temporary code word 1 are “1100” and the first 4 bits of the temporary code 2 are “0000,” these bits are converted to “0110” and “1110” respectively.
According to the Non-Patent Document 3, as outlined above, any code word violating the applicable constraints at a connection between two code words is encoded in keeping with the violation code conversion table of FIG. 3.
The variable-length code is easy to design as a code with a high code rate. On the other hand, the variable-length code tends to entail a maximum error propagation length that is longer than that of a fixed-length code having the same information word length as that code.
The maximum error propagation length refers to a maximum length over which a one-bit error occurring in an encoded sequence propagates to an information sequence. Generally, the maximum error propagation length in effect upon decoding of a fixed-length code is equal to the length of one information word; the maximum error propagation length of a variable-length code typically equals two information words or longer. The longer the information words constituting a maximum error propagation length, the more adversely affected the system in use. Illustratively, the 16/17 code disclosed by the Non-Patent Document 3 above has a maximum error propagation length of two information words at decoding (i.e., 32 bits long).
The shorter the error propagation length of the code, the better. If a code is designed for fixed-length conversion encoding with its information word length kept constant then the error propagation length involved can be shortened. In this case, however, the code rate can often deteriorate because a longer code word length is demanded to obtain desired code constraints. While it is preferable to minimize the error propagation length at decoding of a variable-length code, there has been no encoding method whereby the error propagation length of the variable-length code is limited to one information word or less.
It may also be noted that in the 16/17 code disclosed by the Non-Patent Document 3 above, the maximum transition run (MTR) of 1's is a relatively short three whereas the MTR of 0's (maximum run length) is a relatively long 11.
In order to stabilize the system as a whole including PLL (phase-locked loop) circuitry, it is preferable generally to minimize the maximum run length of the RLL code. For example, if the system adopts an equalization method involving null DC (direct current) components, the maximum run length of the code is proportional to the maximum run length of 0's in expected reproduction signal values. It follows that the larger the maximum run length, the more unstable the PLL circuitry can become in systems with high frequency deviations. In general, magnetic tape systems tend to have higher frequency deviations in reproduced signals than disk systems such as hard disk drives and optical disk systems. In particular, magnetic tape systems employing a rotary transformer arrangement tend to have difficulty in recording low-frequency signals because of the low-frequency cutoff characteristic of the rotary transformer. Thus a prolonged maximum run length of the code will likely cause the magnetic tape system to leave portions of the preceding records undeleted from the magnetic tape during overwrite operations, giving rise to an elevated overwrite noise.
For the reasons outlined above, it may be preferred to utilize an RLL code with its maximum run length made as short as possible depending on the type of the system in use. However, there has been no known encoding method of an RLL code having MTR constraints such that the code rate of encoding is equal to or greater than 16/17 and the maximum run length of the code is 10 or less.
For example, the Non-Patent Document 1 above discusses what kinds of maximum run length constraints are possible for the code (MTR=2) at certain code rates but makes no reference to the codes of MTR=3 and MTR=4. On the other hand, the Non-Patent Document 2 above describes the codes of MTR=3 and MTR=4 but makes no reference to the maximum run lengths of these codes.
That is, according to the techniques proposed so far as outlined above, it is not necessarily clear how the maximum run length can be limited at specific code rates for the codes of MTR=3 and MTR=4.